1. Field of the Invention
This invention relates to cache memory systems and, more particularly, to a mechanism for determining a stack distance histogram of running software for estimating cache miss rates.
2. Description of the Related Art
Cache hit rates have a major impact on processor and computer performance. As a result, the ability to predict cache miss rates accurately is fundamental to both selecting the correct cache organization of a new computer and predicting the performance of that computer. Modern simulation technologies may allow the creation of accurate memory reference traces containing tens of billions of references. There are two main ways in which such memory reference traces can be used to estimate cache hit rates, namely cache simulation and analytical cache models.
Cache simulation provides a memory reference trace as input to the simulation of a specific cache organization or set of cache organizations. Cache simulation has the advantages of providing exact hit rates for a given cache organization and the ability to model arbitrarily complex cache organizations and hierarchies.
However, there may also be disadvantages to using cache simulation. Specifically, cache simulations that use long memory reference traces can be very time consuming, and as a result, they may often be applied to only a small set of possible cache organizations. Another disadvantage of cache simulation may be the lack of insight that the simulations provide into the inherent properties of the reference trace. While the miss rate for a given cache organization may be understood to have some relationship to the reference trace's temporal and spatial locality, the temporal and spatial locality of the trace can only be estimated in a vague and qualitative manner from the cache miss rate.
Although simulation may provide an exact cache miss rate for the given reference trace on the given cache organization, the simulated cache miss rate may not be the best possible estimate of the actual cache miss rate in a future system. For example, cache simulations typically do not provide cold miss rates, since most performance issues are concerned with steady-state, fully-warmed caches. As a result, the error introduced by excessive cold misses is typically not quantified with cache simulations. In addition, the simulated cache miss rate depends on details of the reference trace, such as whether or not a pair of pages map to physical addresses that conflict in the simulated cache, which could easily change when the same application is run again with the same cache organization.
Finally, the extremely large memory reference traces required by cache simulations make it expensive and difficult to store and communicate memory reference information, other than the miss rates for the specific cache organizations, that have been simulated.
Analytical cache models use parameters to characterize a memory reference trace and then apply mathematical operations to those parameters in order to predict cache miss rates. Because the parameters are typically far smaller than the reference trace itself, analytical models can greatly reduce the time required to calculate the miss rate for a given cache organization. In addition, the parameters that characterize the reference trace may give insight into the inherent properties of the trace.